The present invention relates to an apparatus and method for interleaving and deinterleaving data transmitted in a communication system and, more particularly, in a communication system employing turbo codes.
Transmission of digital data is inherently prone to noise and interference that may introduce errors into the transmitted data. Accordingly, error detection schemes are utilized in the art to determine whether errors have been introduced into transmitted data. Examples of such schemes include, for example, adding a cyclic redundancy check (CRC) field to a data packet or frame to determine errors based on comparison of a sum of the data received with a checksum in the CRC field.
Another approach to mitigating the effects of errors introduced into transmitted data is the use of forward error correction such as convolutional codes, which, when introduced to a data frame, allow a receiver of the received data to correctly determine the transmitted data even when errors may have occurred during transmission. Convolutional codes introduce redundancy into the transmitted data and pack the transmitted data into packets in which the value of each bit is dependent on earlier bits in the sequence. Hence, when an error occurs the receiver can reconstruct the original data by tracing back possible sequences in the received data. Further improvement of the performance of a transmission channel can be achieved by using channel interleavers with convolutional coding schemes, which the entire original packet through the use of interleaving and can, thus, more readily be overcome during decoding of the coded data. Further improvements have included multiple-component codes that encode the packet more than once either in parallel or in series. As an example, the prior art is known to employ an error correction scheme that uses at least two concatenated rescursive systematic convolutional coders in parallel and is commonly referred to as “turbo coding”.
There exist many variations of turbo coders, but most types of turbo coders use multiple encoders in parallel separated by interleaving steps. Turbo codes get their performance advantage over convolutional codes through the iterative decoding process. Turbo codes provides performance with respect to noise tolerance in a communication system that was previously unavailable in the prior art. Specifically, turbo coding allows communications at levels of energy-per-bit per noise power spectral density (Eb/N0) that were previously unacceptable using prior art forward error correction schemes.
The performance of turbo codes is sensitive to the interleavers used between the encoders. Previous interleaving schemes used for turbo encoders have included employment of a linear congruentional sequence interleaver requiring look up tables containing coefficients and other values used by a linear congruentional sequence interleaver to calculate row and column indexes. This system, however, requires a large amount of memory and, thus, is less effective in efficiently utilizing system resources.
Based on the problems with prior art interleavers, there is a need for an interleaving scheme within a turbo encoded communication system that is capable of receiving and interleaving any N number of bits in a transmission frame while efficiently utilizing system resources.